// 有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，
// 并且房间里可能有一些钥匙能使你进入下一个房间。
// 在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，
// 每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。
// 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
// 最初，除 0 号房间外的其余所有房间都被锁住。
// 你可以自由地在房间之间来回走动。
// 如果能进入每个房间返回 true，否则返回 false。

// 暴露接口
function canVisitAllRooms(rooms: number[][]): boolean {
  const openMap: boolean[] = new Array(rooms.length).fill(false);// 初始化记录表
  openMap[0] = true;// 0号房间已经默认打开
  for (let i = 0; i < rooms[0].length; i++) {
    // 从0号房间开始搜索
    canVisitAllRooms_DFS(rooms[0][i], openMap, rooms);
  }
  for (let room of openMap) {// 深度优先搜索算法结束查看记录表
    if (room === false) {
      return false;
    }
  }
  return true;
}

// 深度优先遍历
function canVisitAllRooms_DFS(
  start: number,
  openMap: boolean[],
  rooms: number[][]
) {
  if (openMap[start] === true) {
    // 递归出口：当前房间已经被访问过
    return;
  }
  openMap[start] = true;
  for (let key of rooms[start]) {
    canVisitAllRooms_DFS(key, openMap, rooms);
  }
}

// 这道题目是一道看起来复杂实际上书写难度并不大的题目。
// 首先明确这之间的过程基本可以理解为进了一个房间->拿到房间中的一把钥匙
// 钥匙可用就打开下一个房间重复上述操作，若没钥匙或者之前这个房间已经去过了就不做操作
// 明显可以使用深度优先搜索算法来进行模拟
// 这里需要想到的是：
// 1、我们是需要额外的一个数组来记录每个房间的访问情况
// 2、在深度优先遍历搜索算法的过程中在每个房间我们都需要穷举所有的钥匙进行深度优先搜索
// 3、边界条件的考虑，例如说[[]],[[],[1,2]]这种情况下算法要怎么处理
// 完成搜索后我们遍历一遍房间的记录表就可以知道所有房间是否都被访问了